package com.mango.leet.code.hard;

/**
 * 591. 标签验证器
 * @Author: mango
 * @Date: 2022/5/2 9:27 上午
 */

import java.util.*;

/**
 * 给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。合法的代码片段需要遵守以下的所有规则：
 *
 * 代码必须被合法的闭合标签包围。否则，代码是无效的。
 * 闭合标签（不一定合法）要严格符合格式：<TAG_NAME>TAG_CONTENT</TAG_NAME>。其中，<TAG_NAME>是起始标签，</TAG_NAME>是结束标签。起始和结束标签中的 TAG_NAME 应当相同。当且仅当 TAG_NAME 和 TAG_CONTENT 都是合法的，闭合标签才是合法的。
 * 合法的 TAG_NAME 仅含有大写字母，长度在范围 [1,9] 之间。否则，该 TAG_NAME 是不合法的。
 * 合法的 TAG_CONTENT 可以包含其他合法的闭合标签，cdata （请参考规则7）和任意字符（注意参考规则1）除了不匹配的<、不匹配的起始和结束标签、不匹配的或带有不合法 TAG_NAME 的闭合标签。否则，TAG_CONTENT 是不合法的。
 * 一个起始标签，如果没有具有相同 TAG_NAME 的结束标签与之匹配，是不合法的。反之亦然。不过，你也需要考虑标签嵌套的问题。
 * 一个<，如果你找不到一个后续的>与之匹配，是不合法的。并且当你找到一个<或</时，所有直到下一个>的前的字符，都应当被解析为 TAG_NAME（不一定合法）。
 * cdata 有如下格式：<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范围被定义成 <![CDATA[ 和后续的第一个 ]]>之间的字符。
 * CDATA_CONTENT 可以包含任意字符。cdata 的功能是阻止验证器解析CDATA_CONTENT，所以即使其中有一些字符可以被解析为标签（无论合法还是不合法），也应该将它们视为常规字符。
 *
 * 输入: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
 *
 * 输出: True
 *
 * 输入: "<A>  <B> </A>   </B>"
 * 输出: False
 */
public class LC591 {
    public static void main(String[] args) {
        //String code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>";
        //String code = "<DIV>This is the first line <![CDATA[<div>]]><DIV>";
        //String code = "<DIV>  unmatched start tag <B>  and unmatched end tag </C>  </DIV>";
        //String code = "<DIV>>>  ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>";
        //String code = "<A>  <B> </A>   </B>";
        // String code = "<DIV>  unmatched <  </DIV>";
        //String code = "<DIV>This is the first line <![CDATA[<<<<<<<]]></DIV>";
        //String code = "<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>";
        //String code = "<![CDATA[wahaha]]]><![CDATA[]> wahaha]]>";
        //String code = "<A></A><B></B>";
        //String code = "<A><A>/A></A></A>";
        //String code = "<A>  <B> </A>   </B>";
        //String code = "<DIV>This is the first line <![CDATA[<div>]]></DIV>";
        //String code = "123456";
        //String code = "<A";
        //String code = "<A><B><![CDATA[<B></A>]]></B></A>";
        String code = "<A></A>";
        System.out.println(new Solution().isValid(code));
    }
    static class Solution {
        // 栈 + 元素匹配
        // 1. 如果是cdata开头的，则寻找后面的cdata end，没有匹配的返回false
        // 2. 如果是以< 开头的，后一位不是/则为开始标签，放入到栈；如果是/则为结束标签，和栈里元素匹配。不匹配或者匹配后栈空且字符串还未处理完的直接返回false
        // 3. 验证开始标签的合法性，不能有特殊字符，长度1到9
        public boolean isValid(String code) {
            if(code.indexOf("<") != 0){
                return false;
            }
            String cdataStart = "<![CDATA[";
            String cdataEnd = "]]>";
            Deque<String> deque = new LinkedList<>();
            // 找开始标签
            int n = code.length();
            int i = 0;
            while (i<n){
                // 是cdata
                if(i+cdataStart.length() < n && code.substring(i,i+cdataStart.length()).equals(cdataStart)){
                    // 在后续字符串内找end
                    int hasEnd = code.indexOf(cdataEnd, i + cdataStart.length());
                    // 未找到end的匹配
                    if(hasEnd == -1){
                        return false;
                    }else{
                        i = hasEnd + cdataEnd.length()-1;
                        // 匹配完后栈内为空了，但是字符串还没遍历完，不合法
                        if (deque.isEmpty() && i < n) {
                            return false;
                        }
                    }
                }
                else if(code.charAt(i) == '<'){
                    // 后一位是斜杠，则是结束标签
                    if(i+1 >= n){
                        return false;
                    }
                    if (code.charAt(i + 1) == '/') {
                        int index = code.indexOf(">", i);
                        String tag = code.substring(i, index + 1);
                        i = index + 1;
                        if(deque.isEmpty()){
                            return false;
                        }
                        // 匹配
                        if (deque.peekLast().toUpperCase().equals(tag.replace("/", ""))) {
                            deque.pollLast();
                            // 匹配完后栈内为空了，但是字符串还没遍历完，不合法
                            if (deque.isEmpty() && i < n) {
                                return false;
                            }
                        } else {
                            return false;
                        }
                    } else {
                        // 是开始标签,加入到栈
                        int index = code.indexOf(">", i);
                        if(index == -1){
                            return false;
                        }
                        String tag = code.substring(i, index + 1);
                        // 校验合法性，不能有特殊字符，长度1到9
                        if(tag.length()<3 || tag.length()>11){
                            return false;
                        }
                        boolean check = true;
                        for(int j=1;j<tag.length()-1;j++){
                            // '<','>','/','!','[',']'和' '
                            if(tag.charAt(j) == '!'
                                    || tag.charAt(j) == '/'
                                    || tag.charAt(j) == '<'
                                    || tag.charAt(j) == '>'
                                    || tag.charAt(j) == ']'
                                    || tag.charAt(j) == '['
                                    || tag.charAt(j) == ' '){
                                check = false;
                                break;
                            }
                        }
                        if(!check){
                            return false;
                        }
                        i = index;
                        deque.addLast(tag);
                    }
                }else{
                    i++;
                }
            }
            return deque.isEmpty();
        }
    }
}
